package com.jinan.algorithm.monotonicStack;

import java.util.Stack;

// 单调栈
// 当找上一个更大/小元素时，可以维护一个单调栈。
public class monotonicStackTest {
    public static void main(String[] args) {
        String input = "[v1,v2,[v1,v2],v3]";
        Result result = validateArrayString(input);
        if (result.isValid) {
            System.out.println("合法的数组字符串");
        } else {
            System.out.println("不合法的数组字符串，最长合法前缀: " + result.longestValidPrefix);
        }
    }

    private static Result validateArrayString(String input) {
        Stack<Character> stack = new Stack<>();
        StringBuilder longestValidPrefix = new StringBuilder();
        boolean valid = true;
        int count = 0; // 记录元素数量

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            if (c == '[') {
                stack.push(c);
                count = 0; // 新的数组开始
                longestValidPrefix.append(c);
            } else if (c == ']') {
                if (stack.isEmpty()) {
                    valid = false; // 找不到匹配的左括号
                    break;
                }
                stack.pop();
                longestValidPrefix.append(c);
                if (count == 0) {
                    valid = false; // 数组内不能没有元素
                    break;
                }
            } else if (c == ',') {
                if (stack.isEmpty() || longestValidPrefix.length() == 0) {
                    valid = false; // 在无效状态下遇到逗号
                    break;
                }
                longestValidPrefix.append(c);
            } else {
                // 处理元素
                longestValidPrefix.append(c);
                count++; // 记录元素数量
            }
        }

        // 检查栈是否为空
        if (!stack.isEmpty()) {
            valid = false; // 有未匹配的左括号
        }

        return new Result(valid, valid ? input : longestValidPrefix.toString());
    }

    private static class Result {
        boolean isValid;
        String longestValidPrefix;

        Result(boolean isValid, String longestValidPrefix) {
            this.isValid = isValid;
            this.longestValidPrefix = longestValidPrefix;
        }
    }

}


